package qsc.algorithm.pack;

/**
 * @auther QiuShangcheng
 * @create 2021/4/15
 */

public class Pack01 {
    public static void main(String[] args) {
        int[] weight = {1,4,3};
        int[] val = {1500,3000,2000};
        int i = pack01(4, 3, weight, val);
        System.out.println(i);
    }


    /**
     *01背包(动态规划算法)
     *
     * @param V 背包总容量
     * @param N 物品种类
     * @param weight 物品重量
     * @param val 物品价值
     * @return
     */
    public static int pack01(int V, int N, int[] weight, int[] val){
        //初始化状态转移数组
        int[][] dp = new int[N+1][V+1];
        for (int i = 1; i < N + 1; i++){
            for (int j = 1;j < V + 1;j ++){
                //如果当前背包容量j小于当前第i个物品的总量weight[i-1]
                if (weight[i-1] > j){
                    //则上一次的最大价值仍适用当前
                    dp[i][j] = dp[i-1][j];
                }else {//则上一次的最大价值不适用当前，需要重新规划
                    dp[i][j] = Math.max(dp[i - 1][j],val[i - 1] + dp[i - 1][j - weight[i - 1]]);
                }
            }
        }
        int j=V;
        String numStr="";
        for(int i=N;i>0;i--){
            //若果dp[i][j]>dp[i-1][j],这说明第i件物品是放入背包的
            if(dp[i][j]>dp[i-1][j]){
                numStr = i+" "+numStr;
                j=j-weight[i-1];
            }
            if(j==0)
                break;
        }
        System.out.println(numStr);
        return dp[N][V];
    }
}
